#ifndef LNKLS_H_
#define LNKLS_H_

#include <cstddef>
#include <initializer_list>
#include <string>
#include <type_traits>


namespace lxj
{

template<class T,
         std::enable_if_t<std::is_arithmetic_v<T> || std::is_same_v<T, std::string>, int> = 0>
struct Node {   // 表示单向链表时，只启用_right表示next指针
    T     _value;
    Node* _right;
    Node* _left;

    Node() : _value(T{}), _right(nullptr), _left(nullptr) {}
    Node(const T& value, Node* right, Node* left) : _value(value), _right(right), _left(nullptr) {}
    ~Node() { _left = _right = nullptr; }
};

template<class T>
class LinkList {
    Node<T>* _head;
    size_t   _len;

private:
    void destroyOne(size_t index)
    {
        if (index > _len) return;
        index -= 1;
        auto cur      = _head;
        auto del_node = cur->_right;
        while (index--) {
            del_node = del_node->_right;
            cur      = cur->_right;
        }
        cur->_right = del_node->_right;
        delete del_node;
        del_node->_right = nullptr;
        _len -= 1;
    }

public:
    LinkList() : _head(nullptr), _len(0) {}
    LinkList(const std::initializer_list<T>& il)
    {
        if (il.size() == 0) {
            _head = nullptr;
            _len  = 0;
            return;
        }
        _head    = new Node<T>(*il.begin(), nullptr, nullptr);
        auto cur = _head;
        for (auto p = il.begin() + 1; p != il.end(); p++) {
            cur->_right = new Node<T>(*p, nullptr, nullptr);
            cur         = cur->_right;
        }
        _len = il.size();
    };

    template<class Iter>
    LinkList(Iter first, Iter last)
    {
        std::_Adl_verify_range(first, last);
        auto       ufirst = std::_Get_unwrapped(first);
        const auto ulast  = std::_Get_unwrapped(last);
        using type        = std::remove_cv_t<std::remove_pointer_t<decltype(ufirst)>>;
        static_assert(std::is_same_v<T, type>, "模板类型参数不匹配");

        _head    = new Node<T>(*ufirst, nullptr, nullptr);
        _len     = ulast - ufirst;
        auto cur = _head;
        for (auto p = ufirst + 1; p != ulast; p++) {
            cur->_right = new Node<T>(*p, nullptr, nullptr);
            cur         = cur->_right;
        }
    }

    LinkList(const LinkList&) = delete;
    LinkList(LinkList&& other) noexcept : _head(other._head), _len(other._len)
    {
        other._head = nullptr;
    }
    LinkList& operator=(LinkList&& other) noexcept
    {
        if (this == &other) return *this;
        _head       = other._head;
        _len        = other._len;
        other._head = nullptr;
        return *this;
    }

    ~LinkList()
    {
        if (_head == nullptr) return;
        while (_head->_right != nullptr) {
            destroyOne(1);
        }
        delete _head;
        _head = nullptr;
        _len  = 0;
    }

public:
    Node<T>* head() const { return _head; }
    size_t   size() const { return _len; }

    void setSize(size_t value) { _len = value; }

    // 反转链表
    LinkList& inversion()
    {
        if (_len < 2) return *this;

        decltype(_head) cur = _head->_right, new_head = _head, new_tail = nullptr;
        while (cur != nullptr) {
            new_head->_right = new_tail;
            new_tail         = new_head;
            new_head         = cur;
            cur              = cur->_right;
        }
        new_head->_right = new_tail;
        _head            = new_head;
        return *this;
    }

    // 合并两个有序链表，会将other置空
    LinkList& merge2linkList(LinkList&& other)
    {
        if (this->size() == 0 && other.size() == 0) return *this;
        auto merge = [this, &other](const bool b) mutable {
            decltype(_head) new_head = nullptr;
            if (b) {
                auto short_head = _head->_value < other.head()->_value ? _head : other.head();
                auto long_head  = short_head == _head ? other.head() : _head;
                auto cur        = short_head;
                new_head        = short_head;
                _head           = short_head;
                short_head      = short_head->_right == nullptr ? short_head : short_head->_right;
                while (short_head != nullptr && long_head != nullptr) {
                    cur->_right = short_head->_value <= long_head->_value ? short_head : long_head;
                    cur         = cur->_right;
                    cur == short_head ? short_head = short_head->_right
                                              : long_head  = long_head->_right;
                }
                cur->_right = short_head == nullptr ? long_head : short_head;
                _len += other.size();
            }
            else {
                auto short_head = _head->_value < other.head()->_value ? _head : other.head();
                auto long_head  = short_head == _head ? other.head() : _head;
                auto cur        = long_head;
                new_head        = long_head;
                _head           = long_head;
                long_head       = long_head == nullptr ? long_head : long_head->_right;
                while (short_head != nullptr && long_head != nullptr) {
                    cur->_right = short_head->_value >= long_head->_value ? short_head : long_head;
                    cur         = cur->_right;
                    cur == short_head ? short_head = short_head->_right
                                              : long_head  = long_head->_right;
                }
                cur->_right = short_head == nullptr ? long_head : short_head;
                _len += other.size();
            }
            return new_head;
        };

        if (_len == 1 && other.size() == 1) {
            auto head_1    = _head->_value < other.head()->_value ? _head : other.head();
            auto head_2    = head_1 == _head ? other.head() : _head;
            head_1->_right = head_2;
            _len           = 2;
            return *this;
        }
        else if (_len == 1 || other.size() == 1) {
            auto       short_head = _len < other.size() ? _head : other.head();
            auto       long_head  = short_head == _head ? other.head() : _head;
            const bool b          = long_head->_value < long_head->_right->_value ? true : false;
            _head                 = merge(b);
            return *this;
        }
        else {
            bool b      = true;
            auto head_1 = _head, head_2 = other.head();
            while ((head_1->_value == head_1->_right->_value ||
                    head_2->_value == head_2->_right->_value) &&
                   (head_1 != nullptr || head_2 != nullptr)) {
                if (head_1->_value != head_1->_right->_value) {
                    b = head_1->_value < head_1->_right->_value ? true : false;
                    break;
                }

                if (head_2->_value != head_2->_right->_value) {
                    b = head_2->_value < head_2->_right->_value ? true : false;
                    break;
                }
                head_1 = head_1 == nullptr ? head_1 : head_1->_right;
                head_2 = head_2 == nullptr ? head_2 : head_2->_right;
            }
            if (head_1 != nullptr && head_1->_right != nullptr &&
                head_1->_value != head_1->_right->_value) {
                b = head_1->_value < head_1->_right->_value ? true : false;
            }
            else if (head_2 != nullptr && head_2->_right != nullptr &&
                     head_2->_value != head_2->_right->_value) {
                b = head_2->_value < head_2->_right->_value ? true : false;
            }
            else {
                b = b;
            }
            _head = merge(b);
        }
        other._head = nullptr;
        return *this;
    }

    // 划分链表
    /*给定一个链表 ll 和一个数字num，让 ll 中 <num 的放左边，>=num 的放右边，要求维持 ll
     * 节点中的稳定性*/
    template<class Num,
             std::enable_if_t<std::is_integral_v<Num> && std::is_same_v<T, Num>, int> = 0>
    LinkList& partitionLinkList(Num num)
    {
        decltype(_head) leftHead = nullptr, leftTail = nullptr;
        decltype(_head) rightHad = nullptr, rightTail = nullptr;
        auto            cur = _head;
        while (cur != nullptr) {
            if (cur->_value < num) {
                if (leftHead == nullptr) {
                    leftHead = cur;
                    leftTail = leftHead;
                }
                else {
                    leftTail->_right = cur;
                    leftTail         = leftTail->_right;
                }
                cur              = cur->_right;
                leftTail->_right = nullptr;
            }
            else {
                if (rightHad == nullptr) {
                    rightHad  = cur;
                    rightTail = rightHad;
                }
                else {
                    rightTail->_right = cur;
                    rightTail         = rightTail->_right;
                }
                cur               = cur->_right;
                rightTail->_right = nullptr;
            }
        }
        leftHead != nullptr ? leftTail->_right = rightHad : leftHead = rightHad;
        _head = leftHead;
        return *this;
    }
};

// 将两个链表相加
/*如有两个数字466,438，以6->6->4和8->3->4的链表形式给出，将其相加，得到884，以8->8->4形式返回*/
template<class Num, std::enable_if_t<std::is_integral_v<Num>, int> = 0>
LinkList<Num> addTwoNumbers(const LinkList<Num>& ll_1, const LinkList<Num>& ll_2)
{
    LinkList<Num>         ans;
    decltype(ll_1.head()) cur    = nullptr;
    size_t                len    = 0;
    Num                   carry  = Num();
    auto                  head_1 = ll_1.head();
    auto                  head_2 = ll_2.head();
    for (Num sum = Num(), val = Num(); head_1 != nullptr || head_2 != nullptr;
         head_1     = head_1 == nullptr ? nullptr : head_1->_right,
             head_2 = head_2 == nullptr ? nullptr : head_2->_right) {
        sum = (head_1 == nullptr ? 0 : head_1->_value) + (head_2 == nullptr ? 0 : head_2->_value) +
              carry;
        val   = sum % 10;
        carry = sum / 10;
        if (ans.head() == nullptr) {
            ans = std::move(LinkList<Num>({val}));
            cur = ans.head();
            len += 1;
        }
        else {
            cur->_right = new Node<Num>(val, nullptr, nullptr);
            cur         = cur->_right;
            len += 1;
        }
    }
    if (carry == 1) {
        cur->_right = new Node<Num>(1, nullptr, nullptr);
        len += 1;
    }
    ans.setSize(len);
    return ans;
}

}   // namespace lxj

#endif